#include <iostream>
#include <vector>
#include <map>
using namespace std;

//并查集
template<class T>
class UnionFindSet{
public:
    UnionFindSet(size_t n)
        :_ufs(n,-1)
    {}

    void Union(int x, int y){
        int root1 = FindRoot(x);
        int root2 = FindRoot(y);

        //如果本身就在一个集合内就没必要合并
        if(root1 == root2) return;
        //小的合并大的，这个可以不加
        if(root1 > root2) swap(root1, root2);

        _ufs[root1] +=_ufs[root2];
        _ufs[root2] = root1;
    }

    int FindRoot(int x){
        int parent = x;
        while(_ufs[parent] >= 0) parent = _ufs[parent];

        return parent;
    }

    //是否在同一个集合
    bool InSet(int x, int y){
        return FindRoot(x) == FindRoot(y);
    }

    //集合的数量
    size_t SetSize(){
        size_t size = 0;
        for (size_t i = 0; i < _ufs.size(); i++)
        {
            if (_ufs[i] < 0) 
            {
                ++size;
            }
        }
        return size;
        
    }
private:
    vector<T> _ufs;    
};